LeetCode 337、打家劫舍III

一、题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。

这个地区只有一个入口，我们称之为根。

除了“根”之外，每栋房子有且只有一个“父“房子与之相连。

一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 打家劫舍III（ LeetCode 337 ）：https://leetcode-cn.com/problems/house-robber-iii/submissions/
class Solution {
    
    public int rob(TreeNode root) {

        // 每个节点都有两种选择：偷、不偷
        // 从叶子节点开始判断，直到来到根节点
        int[] res = chooseNode(root);
        
        // 选择当前节点偷和不偷抉择时的较大值
        return Math.max(res[0], res[1]);
    }

    private int[] chooseNode(TreeNode node) {
        // 递归终止条件
        // 即在叶子节点的时候，叶子节点的左右子节点为 null
        // 继续调用下去就会返回给叶子节点，它的左右子树的选择的金额都是 0
        if (node == null) {
            return new int[]{0, 0};
        }

        // 否则的话，说明当前节点有值
        // 需要判断，当前节点是偷还是不偷
        
        // 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
        // 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
        // 3、如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和

        // dp[0] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【不偷】 node 这个节点的策略
        // dp[1] 表示的是以当前 node 为根节点的子树能够偷取的最大金额，并且此时采取【偷】 node 这个节点的策略
        int[] dp = new int[2];

        // 先去计算左子节点的选择
        int[] left = chooseNode(node.left);

        // 再去计算右子节点的选择
        int[] right = chooseNode(node.right);

    
        // 如果选择不偷，那么可以偷左右子节点，这个时候的最大金额为左右子节点最大金额之和
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 1、如果选择偷，那么左子节点不能偷，这个时候需要获取不偷左子节点时的最大金额
        // 2、如果选择偷，那么右子节点不能偷，这个时候需要获取不偷右子节点时的最大金额
        // 3、再加上当前节点的金额
        dp[1] = left[0] + right[0] + node.val;

        return dp;
    }
}